<?php

$ar = [5, 8, 6, 4, 12, 5, 3, 1, 89, 54];
echo "input: <br/>";
print_r(json_encode($ar));
echo "<br/>";
echo "<br/>";
$ar = merge($ar);
echo "result: <br/>";
print_r(json_encode($ar));
echo "<br/>";
echo "<br/>";

function merge(array $ar, $len = null)
{
    /*
     *  归并排序实现思路：
     *    1. 拆分左右两部分数组
     *    2. 排序合并
     *    3. 归并排序的本质上是一种分治算法的解法
     */

    if ($len === null) {
        $len = count($ar);
    }

    if ($len <= 1) {
        return $ar;
    }

    $mid   = (int)($len / 2);
    $left  = array_slice($ar, 0, $mid);
    $right = array_slice($ar, $mid);

    echo "left:";
    print_r(json_encode($left));
    echo " -- right:";
    print_r(json_encode($right));
    echo "<br/>";

    $left  = merge($left);
    $right = merge($right);

    $merge = [];

    $leftLen  = count($left);
    $rightLen = count($right);

    $i = $j = 0;
    while (count($merge) < $leftLen + $rightLen) {
        if ($i < $leftLen && ($j === $rightLen || $left[$i] <= $right[$j])) {
            $merge[] = $left[$i];
            $i++;
        } else if ($j < $rightLen && ($i === $leftLen || $left[$i] > $right[$j])) {
            $merge[] = $right[$j];
            $j++;
        }
    }

    echo " merge:";
    print_r(json_encode($merge));
    echo "<br/>";

    return $merge;
}